#include <stdlib.h>
#include <stdio.h>

struct node {
    struct node * _lchild;
    struct node * _rchild;
    int _data;
};
typedef struct node node;

#define MAX_DEPTH 100

// reference:
// http://topic.csdn.net/t/20051210/21/4451313.html
// int   found=FALSE;  
// Bitree*   Find_Near_Ancient(Bitree   T,Bitree   p,Bitree   q)  
// {  
//     Bitree   pathp[   100   ],pathq[   100   ];  
//     Findpath(T,p,pathp,0);  
//     Findpath(T,q,pathq,0);  
//     for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);  
//     return   pathp[--i];  
// }  
// void   Findpath(Bitree   T,Bitree   p,Bitree   path[   ],int   i)  
// {  
//     if(T==p)  
//     {  
// 	found=TRUE;  
// 	return;    
//     }  
//     path[i]=T;  
//     if(T->lchild)   Findpath(T->lchild,p,path,i+1);    
//     if(T->rchild&&!found)   Findpath(T->rchild,p,path,i+1);  
//     if(!found)   path[i]=NULL;  
// }

// return 1 for success, 0 for failure
int find_reach_path(const node * root, const int d, node * path[], int start)
{
    if (root->_data == d) { 
	path[start] = NULL; return 1; 
    }

    path[start] = (node*)root;
    if (root->_lchild && find_reach_path(root->_lchild, d, path, start+1))
	return 1;
    if (root->_rchild && find_reach_path(root->_rchild, d, path, start+1))
	return 1;
    return 0;
}

// return NULL for failure, otherwise a non-null pointer
node * find_nearest_common_ancestor(const node * root, const int d1, const int d2)
{
    int i;
    node * pathp[MAX_DEPTH], * pathq[MAX_DEPTH];
    pathp[0] = pathq[0] = NULL;	// avoid segment fault caused by return pathp[--i] when d1 or d2 equals to root->_data

    if (!root) return NULL;
    if (!find_reach_path(root, d1, pathp, 1)) return NULL;
    if (!find_reach_path(root, d2, pathq, 1)) return NULL;

    for (i = 1; pathp[i] && pathq[i] && pathp[i] == pathq[i]; i++)
       ;

    return pathp[--i];
}

void preorder(node * root)
{
    if (!root) return;

    printf("%d\n", root->_data);
    preorder(root->_lchild);
    preorder(root->_rchild);
}

void postorder(node * root)
{
    if (!root) return;

    postorder(root->_lchild);
    postorder(root->_rchild);
    printf("%d\n", root->_data);
}

int main()
{
    node bt[5] = {
	{NULL, NULL, 1},
	{NULL, NULL, 2},
	{NULL, NULL, 3},
	{NULL, NULL, 4},
	{NULL, NULL, 5},
    };
    //bt[0] = {&bt[1], &bt[2], 20};
    //bt[1] = {&bt[3], &bt[4], 8};
    //bt[2] = {&bt[5], &bt[6], 22};
    //bt[3] = {NULL, NULL, 4};
    //bt[4] = {&bt[7], &bt[8], 12};
    //bt[5] = {NULL, NULL, 21};
    //bt[6] = {NULL, NULL, 23};
    //bt[7] = {NULL, NULL, 10};
    //bt[8] = {NULL, NULL, 14};
    bt[0]._lchild = &bt[1]; bt[0]._rchild = &bt[2]; 
    bt[1]._rchild = &bt[3]; bt[2]._lchild = &bt[4];

    //preorder(&bt[0]);
    postorder(&bt[0]);

    node * nca = NULL;
    nca = find_nearest_common_ancestor(&bt[0], 5, 5);
    if (!nca)
	printf("NULL lca\n");
    else
	printf("lca: %d\n", nca->_data);
    
    return 0;
}
